/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2022并保留所有权利。
 * Copyright 2022, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.suanfa.test.teshuawei.test.双指针;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Title：NC41-最长无重复, 数组中最长连续无重复长度
 * Description：双指针、Set、Map
 * @author WZQ
 * @version 1.0.0
 * @date 2021/2/24
 */
public class NC41 {

    /**
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        int length = arr.length;
        if (length < 2){
            return length;
        }
        // 双指针
        // j纪录尾部，遍历到尾部
        // i纪录头部，遇到重复的向后遍历删除
        int max = 0, i = 0, j = 0;
//        Map<Integer, Integer> map = new HashMap<>();
//        while (j < length){
//            //包含
//            if (map.containsKey(arr[j])){
//                //存在相同的元素
//                // 123412 1234 i=0 j=4,
//                i = map.get(arr[j])
//            }else {
//                //不包含
//                map.put(arr[j], j);
//            }
//            max = Math.max(max, j - i + 1);
//            j++;
//        }

        Set<Integer> set = new HashSet<>();
        while (j < length){
            //包含
            if (set.contains(arr[j])){
                //头指针, 删除到重复元素的下一个位置
                set.remove(arr[i]);
                i ++;
            }else {
                //不包含
                set.add(arr[j]);
                j ++;
            }
            max = Math.max(max, set.size());
        }
        return max;
    }

}
